package A1_栈和队列;

import java.util.Deque;
import java.util.LinkedList;

public class LC_239滑动窗口最大值_数组 {
    public static void main(String[] args){
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        System.out.println(maxSlidingWindow(nums,k));
    }
    public static int[] maxSlidingWindow(int[] nums, int k) {
        //存储数组元素的下标
        // 队列表示滑动窗口
        Deque<Integer> myque=new LinkedList<>();
        int resIndex=0;
        int[] res=new int[nums.length-k+1];
        for(int i=0;i<nums.length;i++){
            //头尾尾头口诀
            // 1.头:清理超期元素(清理i-k位置的元素)
            if(!myque.isEmpty() && myque.peekFirst()==i-k)
                myque.pollFirst();
            // 2.尾:维护单调递减队列(清除队列内<新入队元素的元素)
            while(!myque.isEmpty() && nums[i]>=nums[myque.peekLast()]){
                myque.pollLast();
            }
            // 3.尾:新元素入队
            myque.offerLast(i);
            // 4.头:获取滑动窗口最大值(返回头部元素,i>=k-1时)
            if(i>=k-1)
                res[resIndex++]=nums[myque.peekFirst()];
        }
        return res;
    }
}
